# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
root=TreeNode(21,None,None)
root.left=TreeNode(7,None,None)
root.left.left=TreeNode(1,None,None)
root.left.left.left=TreeNode(3,None,None)
root.left.right=TreeNode(1,None,None)
root.left.left.right=TreeNode(3,None,None)
root.right=TreeNode(14,None,None)
root.right.left=TreeNode(2,None,None)
root.right.right=TreeNode(2,None,None)
def dfs(root):
    print("--",root.val,"--")
    if root.left==None and root.right==None:
        print("当前节点是一个叶子节点,对于的val=",root.val)
        return 0
        # return 0
    if root.left!=None:
        leftSum=dfs(root.left)
        root.val+=root.left.val
        leftValue=root.left.val
    else:
        leftSum=0
        leftValue=0
    if root.right!=None:
        rightSum=dfs(root.right)
        root.val+=root.right.val
        rightValue=root.right.val
    else:
        rightSum=0
        rightValue=0
    print("right:",rightSum,"left:",leftSum,"root:",abs(root.left.val-root.right.val))
    # root.val+=root.left.val+root.right.val
    return rightSum+leftSum+abs(rightValue-leftValue)

def findTilt(root):
    if root==None:
        return 0
    sum=dfs(root)
    return sum
print(findTilt(root))
